class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}
/**
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 * 返回以nums中的最大值为根的最大二叉树
 * @param nums 
 */
const constructMaximumBinaryTree = (nums: number[]): TreeNode | null => {
    const len = nums.length;

    // 数组为空, 返回空
    if (len === 0) return null

    // 数组为空
    if (len === 1) return new TreeNode(nums[0], null, null)

    // 默认第一项为最大值
    let max = nums[0]

    // 求最大项
    let maxI: number = 0;
    for (let i = 1; i < len; i++) {
        if (nums[i] > max) {
            max = nums[i];
            maxI = i
        }
    }

    // 以max为值构建二叉树
    const root = new TreeNode(max, null, null)


    root.left = maxI - 1 < 0 ? null : constructMaximumBinaryTree(nums.slice(0, maxI))
    root.right = maxI + 1 >= len ? null : constructMaximumBinaryTree(nums.slice(maxI + 1))

    return root;
};

/**
 * 求最大二叉树的每个节点的父节点
 * @param nums 
 */
const constructMaximumBinaryTreeParent = (nums: number[]): number[] => {
    const len = nums.length;

    // 数组为空, 返回空
    if (len === 0) return nums



    let left: number[] = [], // 距离左边的最大
        right: number[] = [], // 距离右边的最大
        stack: number[] = []; // 模拟栈

    // 初始化数组
    for (let i = 0; i < len; i++) {
        left[i] = -1
        right[i] = -1
    }

    // 遍历
    for (let i = 0; i < len; i++) {
        // 处理右边 (当前元素大于栈顶 并且 栈不为空)
        while (nums[stack[stack.length - 1]] < nums[i] && stack.length > 0) {
            right[stack.pop()!] = i
        }

        // 处理左边 (栈中有元素)
        if (stack.length > 0) {
            left[i] = stack[stack.length - 1]
        }

        // 将当前索引放入栈中
        stack.push(i)
    }

    // 构建每一项的父节点
    let p: number[] = []
    for (let i = 0; i < len; i++) {
        if (left[i] === -1 && right[i] === -1) {
            // 根节点
            p[i] = -1;
            continue
        }

        if (left[i] === -1) {
            // 左边没有比其大的, 父节点是右边第一个比它大的
            p[i] = right[i]
        } else if (right[i] === -1) {
            // 右边没有比其大的, 父节点是左边第一个比它大的
            p[i] = left[i]
        } else if (nums[left[i]] < nums[right[i]]) {
            // 距离左边小于距离右边, 父节点是左边
            p[i] = left[i]
        } else {
            p[i] = right[i]
        }
    }

    return p
};

const root = constructMaximumBinaryTreeParent([3, 2, 1, 6, 0, 5])
console.log(root);

export {}